package NewCoder;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class BM39 {
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);
    String Serialize(TreeNode root) {
        if (root == null) return "";

        StringBuilder sb = new StringBuilder();
        // 使用队列进行层序遍历，起始先将 root 放入队列
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            // 每次从队列中取出元素进行「拼接」，包括「正常节点」和「叶子节点对应的首位空节点」
            TreeNode poll = d.pollFirst();
            sb.append(poll.val + "_");
            // 如果取出的节点不为「占位节点」，则继续往下拓展，同时防止「占位节点」不继续往下拓展
            if (!poll.equals(emptyNode)) {
                d.addLast(poll.left != null ? poll.left : emptyNode);
                d.addLast(poll.right != null ? poll.right : emptyNode);
            }
        }
        return sb.toString();
    }
    TreeNode Deserialize(String str) {
        if (str.equals("")) return null;

        // 根据分隔符进行分割
        String[] ss = str.split("_");
        int n = ss.length;
        // 怎么序列化就怎么反序列化
        // 使用队列进行层序遍历，起始先将 root 构建出来，并放入队列
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        for (int i = 1; i < n - 1; i += 2) {
            TreeNode poll = d.pollFirst();
            // 每次从中取出左右节点对应 val
            int a = Integer.parseInt(ss[i]), b = Integer.parseInt(ss[i + 1]);
            // 如果左节点对应的值不是 INF，则构建「真实节点」
            if (a != INF) {
                poll.left = new TreeNode(a);
                d.addLast(poll.left);
            }
            // 如果右节点对应的值不是 INF，则构建「真实节点」
            if (b != INF) {
                poll.right = new TreeNode(b);
                d.addLast(poll.right);
            }
        }
        return root;
    }
}

